package org.example.myleet.dijkstra;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class DijkstraSolution {

    private static final int N = 3010;
    private static final int INF = 0x3f3f3f3f;

    /**
     * 743【Dijkstra】网络延迟时间
     */
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE;
        //false为未确定的节点
        boolean[] confirmed = new boolean[n + 1];
        //初始化，所有边无穷远
        int[][] g = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                g[i][j] = INF;
            }
        }
        //解析边
        for (int[] edge : times) {
            g[edge[0]][edge[1]] = edge[2];
        }
        //记录信息到达节点最快的时间消耗
        int[] consumption = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            //初始化为无穷
            consumption[i] = INF;
        }
        consumption[k] = 0;
        confirmed[k] = true;
        int remainUnconfirmed = n - 1;
        int curNode = k;
        while (remainUnconfirmed > 0) {
            //从最近一个加入确定分类的节点中取出其发射的所有边
            int[] edges = g[curNode];
            int minDistance = INF;
            int closest = -1;
            //以最近一个加入确定分类的节点，更新其余未确定的节点到源点的最近距离
            for (int i = 1; i <= n; ++i) {
                if (!confirmed[i]) {
                    if (edges[i] < INF) {
                        int newConsume = consumption[curNode] + edges[i];
                        if (consumption[i] > newConsume) consumption[i] = newConsume;
                    }
                    if (minDistance > consumption[i]) {
                        minDistance = consumption[i];
                        closest = i;
                    }
                }
            }
            if (closest == -1) {
                //在有未确定节点的情况下找不到下一轮循环用的节点，说明存在节点不可到达
                return -1;
            }
            //挑选出来离源点最近的节点加入确定节点中，并进入下一个循环
            confirmed[closest] = true;
            remainUnconfirmed--;
            curNode = closest;
        }
        int maxConsume = 0;
        for (int i = 1; i <= n; ++i) {
            if (consumption[i] == Integer.MAX_VALUE) {
                //确定节点中存在无限远距离的节点，说明存在节点不可到达
                return -1;
            }
            //距离最远的节点为网络信息传达到整个网络的最短时间（水桶短板）
            maxConsume = Math.max(maxConsume, consumption[i]);
        }
        return maxConsume;
    }

    //p882
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        //建图
        int[][] graph = new int[N][N];
        for (int i = 0; i < n; i++) Arrays.fill(graph[i], INF);
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u][v] = graph[v][u] = w + 1;
        }
        //朴素Dijkstra
        boolean[] visited = new boolean[n];
        int[] distance = new int[n];
        Arrays.fill(distance, INF);
        distance[0] = 0;
        for (int i = 1; i < n; ++i) {
            int x = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (x == -1 || distance[j] < distance[x])) {
                    //找距离最短的下一个点
                    x = j;
                }
            }
            //标记为访问过点x
            visited[x] = true;
            for (int j = 0; j < n; ++j) {
                //以点x的最短距离更新距离0点的距离
                distance[j] = Math.min(distance[j], distance[x] + graph[x][j]);
            }
        }
        //统计结果
        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (distance[i] <= maxMoves) answer++;
        }
        for (int[] info : edges) {
            int a = info[0], b = info[1], c = info[2];
            //分别代表到达两个点剩余的步数
            int c1 = Math.max(0, maxMoves - distance[a]), c2 = Math.max(0, maxMoves - distance[b]);
            //要么就是覆盖整条边，要么就是一条边没走完
            answer += Math.min(c, c1 + c2);
        }
        return answer;
    }

    /**
     * 1334【Dijkstra】阈值距离内邻居最少的城市
     */
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 0x3f3f3f3f;
        int mnCandidate = 0, mn = n;
        //建图，以及邻接矩阵
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(graph[i], INF);
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u][v] = graph[v][u] = w;
        }
        //对每个店进行一次Dijkstra方法找到其他点到这个点的最短距离
        for (int node = 0; node < n; ++node) {
            //朴素Dijkstra
            boolean[] visited = new boolean[n];
            int[] distance = new int[n];
            //初始化distance数组，即为已知的graph[node]
            System.arraycopy(graph[node], 0, distance, 0, n);
            distance[node] = 0;
            for (int i = 0; i < n; ++i) {
                if (i == node) continue;
                int x = -1;
                for (int j = 0; j < n; ++j) {
                    if (!visited[j] && (x == -1 || distance[j] < distance[x])) {
                        //找距离最短的下一个点
                        x = j;
                    }
                }
                //标记为访问过点x
                visited[x] = true;
                for (int j = 0; j < n; ++j) {
                    //以点x的最短距离更新距离node点的距离
                    distance[j] = Math.min(distance[j], distance[x] + graph[x][j]);
                }
            }
            //已经找到其他点到node点的最短距离，根据threshold统计可以到达的点的数目
            int reachCnt = -1;
            for (int i = 0; i < n; ++i) {
                if (distance[i] <= distanceThreshold) {
                    ++reachCnt;
                }
            }
            if (reachCnt >= 0 && reachCnt <= mn) {
                mn = reachCnt;
                mnCandidate = node;
            }
        }
        return mnCandidate;
    }

    /**
     * 1976【Dijkstra】到达目的地的方案数
     */
    public int countPaths(int n, int[][] roads) {
        int MOD = 1000000007;
        long INF = 0x3f3f3f3f3f3f3fL;
        //建图，以及邻接矩阵
        long[][] graph = new long[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(graph[i], INF);
        for (int[] edge : roads) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u][v] = graph[v][u] = w;
        }
        //朴素Dijkstra
        boolean[] visited = new boolean[n];
        long[] distance = new long[n];
        //初始化distance数组，为从0点到各邻近点的距离
        System.arraycopy(graph[0], 0, distance, 0, n);
        long[] cnt = new long[n];
        distance[0] = 0;
        visited[0] = true;
        cnt[0] = 1L;
        for (int x = 1; x < n; ++x) {
            if (graph[0][x] < INF) cnt[x] = 1;
        }
        for (int i = 1; i < n; ++i) {
            int x = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (x == -1 || distance[j] < distance[x])) {
                    //找距离最短的下一个点
                    x = j;
                }
            }
            //找到距离最近的点，访问点x，标记
            visited[x] = true;
            for (int j = 0; j < n; ++j) {
                //以点x的最短距离更新距离0点的距离
                long newDistance = distance[x] + graph[x][j];
                if (newDistance > INF) continue; //不可到达
                if (distance[j] > newDistance) {
                    //找到更短的路径，以此为有效路径，路径数刷新为继承自cnt[x]
                    distance[j] = newDistance;
                    cnt[j] = cnt[x];
                } else if (distance[j] == newDistance) {
                    //有一样短的路径可以到大点j，也加入有效路径数量中
                    cnt[j] += cnt[x];
                    cnt[j] %= MOD;
                }
            }
        }
        return (int) cnt[n - 1];
    }

    public static void main(String[] args) {
        DijkstraSolution solution = new DijkstraSolution();
        Assert.isTrue(2 == solution.countPaths(5 ,Parser.parse("[[0,1,1],[1,2,4],[0,4,3],[3,2,5],[3,4,1],[3,0,5],[1,3,1]]")));
        Assert.isTrue(1 == solution.countPaths(5 ,Parser.parse("[[0,1,1000000000],[1,2,1000000000],[2,3,1000000000],[3,4,1000000000]]")));
        Assert.isTrue(4 == solution.countPaths(7 ,Parser.parse("[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]")));
    }
}
